/**
 * 优先队列：O(logN) 出队顺序和入队顺序无关, 和优先级有关，可以使用不同的底层实现
 * 堆：最大堆（大顶堆），最小堆（小顶堆）
 * 堆的性质:
 * > 堆是一棵完全二叉树
 * > 堆中某个节点的值， 总是不大于其父节点的值
 */
public class MaxHeap<E extends Comparable<E>> {

    // 使用动态数组存储堆结构
    private Array<E> data;

    public MaxHeap() {
        this(10);
    }

    public MaxHeap(int capacity) {
        data = new Array<>(capacity);
    }

    // 计算父节点索引
    public int parent(int index) {
        if (index == 0) throw new IllegalArgumentException("index-0 doesn't have parent");
        return (index - 1) / 2;
    }

    // 计算左孩子节点索引
    public int left(int index) { return index * 2 + 1; }
    // 计算右孩子节点索引
    public int right(int index) { return index * 2 + 2; }

    public void add(E elem) {
        data.addLast(elem);
        siftUp(data.size() - 1);
    }

    // 上浮动作
    private void siftUp(int k) {
        // k 并不是根节点， 并且大于它的父节点值，执行 siftUp 操作
        while (k > 0 && data.get(k).compareTo(data.get(parent(k))) > 0) {
            data.swap(k, parent(k));
            k = parent(k);
        }
    }

    // 查看堆中存储的最大值（大顶堆的堆顶元素）
    public E findMax() {
        if (data.isEmpty()) throw new IllegalArgumentException("MaxHeap is empty");
        return data.get(0);
    }

    // 取出堆顶元素
    public E extractMax() {
        E elem = findMax();
        data.swap(0, data.size() - 1);
        data.removeLast();
        siftDown(0);
        return elem;
    }

    // 下沉动作
    private void siftDown(int k) {
        while (left(k) < data.size()) { // 左孩子索引小于data.size() => 还有子元素
            int j = left(k);
            if (j + 1 < data.size() && data.get(j + 1).compareTo(data.get(j)) > 0)
                j++;   // 有右孩子， 并且右孩子比左孩子更大， 应当和右孩子进行交换
            // 如果 k 位置元素 >= j位置节点， 可以停止 siftDown， 说明k到了自己的位置
            if (data.get(k).compareTo(data.get(j)) >= 0) break;
            data.swap(k, j);
            k = j; // 更新k, 重新进入循环，执行siftDown计算
        }
    }

    // replace 替换
    public E replace(E elem) {
        E top = data.get(0);
        data.set(0, elem);
        siftDown(0);
        return top;
    }

    // TODO 将一个数据堆化
    // 堆化, 将一个数组, 逐渐整理成堆化
    public void heapify() {

    }

    public int size() { return data.size(); }
    public boolean isEmpty() { return data.isEmpty(); }

    // 0层 1个
    // 1层 2个
    // 3层 4个
    // 4层 8个
    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        res.append("MaxHeap:\n");
        res.append("[");
        for (int i = 0; i < data.size(); i++) {
            res.append(data.get(i));
            if (i != data.size() - 1)
                res.append(", ");
        }
        res.append("]");
        return res.toString();
    }
}

